package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;


/*
农夫约翰正在分配他的N（1 <= N <= 25000）头奶牛中的一些牛去犁地
并将一天视为数轴T（1 <= T <= 1000000）
一头牛干一次活，每头牛只能在一天中的某个时间间隔内进行犁地工作
你的工作是帮助农夫约翰安排一些奶牛轮班，使得选中的牛的工作时间，能全覆盖数轴T
尽可能少的奶牛参与清洁。
如果无法全覆盖T，请打印-1。
输入
第1行：
	1个空格分隔的整数：N和T
第2..N+1行：
	每一行都包含奶牛可以工作的时间线段的开始和结束时间
输出
第1行：农场主约翰需要雇佣的奶牛的最低数量，如果无法全覆盖，则为-1

Sample Input
3 10
1 7
3 6
6 10
Sample Output
2
*/
public class c区间覆盖by贪心 {
	public static void main(String[] args) {
		c区间覆盖by贪心 test = new c区间覆盖by贪心();
		test.useGreedyAlgorithm5();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithm5() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int T = scanner.nextInt();
		Job[] jobs = new Job[N];
		for (int i = 0; i < N; i++) {
			jobs[i] = new Job(scanner.nextInt(), scanner.nextInt());
		}
		Arrays.sort(jobs);
		int res = GreedyAlgorithm5(jobs, N, T);
		System.out.println(res);
	}
	
	/**
	 * 迭代形式
	 * @param jobs
	 * @param N
	 * @param T
	 * @return
	 */
	public int GreedyAlgorithm5(Job[] jobs, int N, int T) {
		int currentStart = 1;
		int currentTerminate = 1;
		int res = 1;
		for (int i = 0; i < N; i++) {
			int start = jobs[i].start;
			int terminate = jobs[i].treminate;
			if (i == 0 && start > 1) {//这里也可以写成：i == 0 && start != 1
				//如果排序后的第一个线段，也是“最早”的线段，都不满足包含数轴的头部的全部区间，那么
				break;//就不值得再循环遍历了，直接退出for循环
			}
			if (start <= currentStart) {//比currentStart还要小的start
				currentTerminate = Math.max(terminate, currentTerminate);//更新最大的terminate
			} else {
				res++;//在当前排好序的Job[]中，已经没有比currentStart还要小的start了；代表需要一头牛A了；这头牛A是“在start比currentStart小的所有牛中terminate最大的”
//				currentStart = currentTerminate + 1;//？
				currentStart = currentTerminate;//？
				if (start <= currentStart) {//因为能走到这个分支，代表当前的start > 旧currentStart；此时的是判断start <= 新currentStart(新currentStart是牛A的terminate)
					currentTerminate = Math.max(terminate, currentTerminate);//通过判断，不要浪费当前的传进来的Job[i],所以更新最大的terminate
				} else {
					break;//不通过，那么代表：因为排序嘛，当前的Job[i] = A已经是较小的了，如果A还大于新currentStart，那已经没有start比新currentStart小了；所以直接break;
				}
			}
			if (currentTerminate >= T) {//如果当前选择的所有的牛，已经实现了全覆盖
				break;//那么不用接着遍历了；相当于提前结束；也就是剪枝
			}
		}
		if (currentTerminate < T) {//for循环遍历完毕，仍然未全覆盖数轴
			return -1;//那么无解
		} else {
			return res;//全覆盖，则输出牛数
		}
	}
	
	/**
	 * 打包类
	 * @author wuqiu
	 */
	private static class Job implements Comparable<Job> {
		int start;
		int treminate;
		public Job(int start, int treminate) {
			this.start = start;
			this.treminate = treminate;
		}
		@Override
		public int compareTo(Job o) {
			int x = this.start - o.start;//按起点排序
			if (x == 0) {
				return this.treminate - o.treminate;//这里谁减谁都一样
				//目前是：起点相同，谁线段长谁靠后
			}
			return 0;
		}
	}
}
